import { testSort, measureSort } from "hy-algokit";

export default function insertionSort(arr: number[]): number[] {
  let n = arr.length;

  for (let i = 1; i < n; i++) {
    let newNum = arr[i];
    let j = i - 1;
    while (arr[j] > newNum && j >= 0) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = newNum;
  }

  return arr;
}

// testSort(insertionSort);
measureSort(insertionSort);

export {};
